#include <iostream>

using namespace std;
#include <vector>


//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int left = -1, right = nums.size();
//        int i = 0;
//        while (i < right)
//        {
//            if (nums[i] == 0)
//            {
//                swap(nums[++left], nums[i]);
//                i++;
//            }
//            else if (nums[i] == 2)
//            {
//                swap(nums[--right], nums[i]);
//            }
//            else i++;
//        }
//    }
//};


//class Solution {
//public:
//    void _sortArray(vector<int>& nums, int begin, int end)
//    {
//        if (begin >= end)
//            return;
//
//        int r = begin + rand() % (end - begin + 1);
//        swap(nums[begin], nums[r]);
//        int key = nums[begin];
//
//        int left = begin - 1, right = end + 1;
//        for (int i = begin; i < right;)
//        {
//            if (nums[i] < key)
//            {
//                swap(nums[++left], nums[i]);
//                i++;
//            }
//            else if (nums[i] > key)
//            {
//                swap(nums[--right], nums[i]);
//            }
//            else i++;
//        }
//
//        _sortArray(nums, begin, left);
//        _sortArray(nums, right, end);
//
//    }
//
//    vector<int> sortArray(vector<int>& nums) {
//        _sortArray(nums, 0, nums.size() - 1);
//
//        return nums;
//    }
//};

class Solution {
public:

    int _findKthLargest(vector<int>& nums, int begin, int end, int k)
    {
        if (begin >= end)
            return nums[begin];

        // int r = begin + rand() % (end - begin + 1);
        // swap(nums[begin], nums[r]);
        int key = nums[begin];

        int left = begin - 1, right = end + 1;
        for (int i = begin; i < right;)
        {
            if (nums[i] < key)
            {
                swap(nums[++left], nums[i]);
                i++;
            }
            else if (nums[i] > key)
            {
                swap(nums[--right], nums[i]);
            }
            else i++;
        }

        if (end - right + 1 >= k)
            return _findKthLargest(nums, right, end, k);
        else if (end - left>= k)   return nums[left + 1];
        else return _findKthLargest(nums, begin, left, k - (end - left));


    }

    int findKthLargest(vector<int>& nums, int k) {
        int ret = _findKthLargest(nums, 0, nums.size() - 1, k);

        return ret;
    }
};

int main()
{
    vector<int> nums = { 3,2,1,5,6,4 };
    Solution().findKthLargest(nums, 2);
    return 0;
}